Date: Tuesday, 14-Jan-97 20:40:13 GMT
Server: NCSA/1.3
MIME-version: 1.0
Content-type: text/html

<HTML>

<HEAD>

<TITLE>CS 575 Syllabus</TITLE>

</HEAD>

<BODY>

<H1>CS 575 - Theoretical Aspects of Computing</H1>
<HR>

<H3><I>COMPUTABILITY </I></H3>

<BLOCKQUOTE>
The NICE Programming Language<BR>
Turing Machines<BR>
A Smaller Programming Language<BR>
Equivalence of the Models<BR>
Machine Enhancement<BR>
The Theses of Church and Turing<BR>
</BLOCKQUOTE>

<H3><I>UNSOLVABILITY </I></H3>

<BLOCKQUOTE>
Arithmetization<BR>
Properties of the Enumeration<BR>
Universal Machines and Simulation<BR>
Solvability and the Halting Problem<BR>
Reducibility and Unsolvability<BR>
Enumerable and Recursive Sets<BR>
</BLOCKQUOTE>

<H3><I>COMPLEXITY </I></H3>

<BLOCKQUOTE>
Measures and Resource Bounds<BR>
Complexity Classes<BR>
Reducibilities and Completeness<BR>
The Classes <i>P</i> and <i>NP</i><BR>
Intractable Problems<BR>
</BLOCKQUOTE>

<H3><I>AUTOMATA </I></H3>

<BLOCKQUOTE>
Finite Automata<BR>
Closure Properties and Nondeterminism<BR>
Regular Sets and Expressions<BR>
Decision Problems for Finite Automata<BR>
Pushdown Automata<BR>
Unsolvable Problems for Pushdown Automata<BR>
Linear Bounded Automata<BR>
</BLOCKQUOTE>

<H3><I>LANGUAGES </I></H3>

<BLOCKQUOTE>
Grammars<BR>
Language Properties<BR>
Regular Languages<BR>
Context Free Languages<BR>
Context Free Language Properties<BR>
Summary<BR>
</BLOCKQUOTE>

</BODY>

</HTML>
